Marginalia — Cuaderno Interactivo Marginalia 02 Groups

Definición Formal de una Ley de Composición

Una ley de composicion sobre un conjunto $S$ es cualquier regla que combina pares de elementos $a, b$ de $S$ para obtener otro elemento $p$ de $S$. Formalmente, se define como una funcion o mapeo de dos varibles que va del producto cartesiano de $S$ consigo mismo hacia $S$:

\[\phi: S \times S \longrightarrow S\]

El elemnto obtenido al aplicar la ley al par ordenado $(a, b)$ se denota comunmente en forma multiplicativa como $ab$ (aunque también se pueden emplear notaciones como $a \times b$, $a \circ b$ o $a + b$)

Es fundamental resaltar desde el punto de vista conceptual que $ab$ representan un unico elemento especifico de $S$; una vez evaluada la composicion, no es posible recuperar o reconstruir de manera unica los elementos originales $a$ y $b$ a partir de del resultado del producto.

—

Propiedades Fundamentales

Asociatividad: Una ley de composicion (escrita multiplicativamente) es asociativa si para cualesquiera elementos de $a, b, c \in S$ se cumple que:

\[(a b) c = a (b c)\]

Donde $(ab)c$ significa que primero se compone $a$ con $b$, y el resultado se compone por la derecha con c.
Conmutatividad: Una ley de composicion es conmutativa si para cualesquiera $a, b \in S$ se cumple que:

\[a b = b a\]

Por convencion matematica, la notacion aditiva $a + b$ se reserva exclusivamente para las leyes que son conmutativas $(a + b = b + a$. La notacion multiplicativa no presupone ni implica conmutatividad.

—

Composicion de Funciones como la Ley Fundamental

La asociatividad es una propiedad mas fundamental que la conmutatividad debido a que la composicion de funciones es intrinsecamente asociativa. Si $T$ es un conjunto y $f$, $g$ son funciones (o mapeos) de $T$ en $T$, se define la composicion $g \circ f$ como mapeo que asigna a cada $t \in T$ el valor $g(f(t))$ (aplicando primero $f$ y luego $g$). La regla de asignacion $(f, g) \mapsto g \circ f$ define una ley de composicion asociativa sobre el conjunto de mapeos $T \to T$.

Ejemplo con un conjunto de dos elementos

Sea $T = {a,b}$. Existen exactamente cuatro mapeos posibles de $T$ en $T$:

Identidad ($i$): $i(a) = a$, $i(b) = b$.

Transposicion (τ): $\tau(a) = b$, $\tau(b) = a$.

Constante α: $\alpha(a) = a$, $\alpha(b) = a$.

Constante β: $\beta(a) = b$, $\beta(b) = b$.

La ley de composicion de funciones de este conjunto {$i, \tau, \alpha, \beta$} se detalla en la siguiente tabla multiplicativa (donde la fila indica el primer mapeo aplicado por la derecha y la columna el segundo aplicando por la izquierda, es decir, el elemento en la fila $f$ y la columna $g$ representa $g \circ f$).

\[\begin{array}{c|cccc} \circ & i & \tau & \alpha & \beta \\ \hline i & i & \tau & \alpha & \beta \\ \tau & \tau & i & \beta & \alpha \\ \alpha & \alpha & \alpha & \alpha & \alpha \\ \beta & \beta & \beta & \beta & \beta \\ \end{array}\]

Esta tabla demustra de forma concreta que la composicion de funciones no es conmutativa, ya que, por ejemplo, $\tau \circ \alpha = \beta$ mientras que $\alpha \circ \tau = \alpha$.

—

Asociatividad Generalizada

Cuando se desea definir el producto de una cadena de $n$ elementos $a_{1}, a_{2}, ... , a_{n}$ utilizando una ley binaria, exiten diversas maneras de agrupar los terminos mediante parentesis. Sin embargo, si la ley es asociativa, todos los agrupamientos posibles conducen al mismo elemento en $S$.

Proposicion 2.1.4 (Teoria de Asociatividad Generalizada)

Sea una ley de composicion asociativa definida sobre un conjunto $S$. Existe una unica manera de definir, para cada entero positivo $n$, un producto de $n$ elementos $a_{1}, ... , a_{n} \in S$, denotado temporalmente por [$a_{1} ... a_{n}$], que satisfaga las siguientes tres propiedades:

$[a_{1}] = a_{1}$ (el producto de un solo elemento es el elemnto mismo).
$[a_{1}a_{2}] = a_{1}a_{2}$ (el producto de dos elementos esta dado directamente por la ley de composicion)
Para cualquier entero $i$ en el rango $1 \le i < n$, se cumple la relacion de reucrrencia.

\[[a_{1} ... a_{n}] = [a_{1} ... a_{i}][a_{i+1} ... a_{n}]\]

—

Demostracion por Induccion Matematica

Procedemos por induccion sobre el numero de elementos $n$.

Base de induccion $n \le 2$: Para $n = 1$ y $n = 2$, el producto esta definido de forma unica por las condiciones (i) y (ii), y se verifica inmediatamente que cumple con (iii) para $n = 2$ (donde la unica particion posible es $i = 1$, dando $[a_{1}a_{2}] = [a_{1}][a_{2}] = a_{1}a_{2}$).
Paso inductivo: Supongamos que el producto de $r$ elementos esta definido de forma unica y satisface la propiedad (iii) para todo $r < n$. Definimos obligatoriamente el producto de $n$ elementos basandonos en la particion en el extremo derecho (cuando $i = n -1$):

\[[a_{1} ... a_{n}_{}] = [a_{1} ... a_{n-1}][a_{n}]\]

Cualquier definicion del producto que pretenda satisfacer la condicion (iii) debe cumplir esta igualdad (evaluando en $i = n -1$). Por lo tanto, si dicho producto existe, es necesariamente unico.

Ahora debemos demostrar que esta definicion cumple con la propiedad (iii) para cualquier otro valor de corte $i < n - 1$:

\[[a_{1} ... a_{n}] = \] \[[a_1 \dots a_n] \stackrel{?}{=} [a_1 \dots a_i][a_{i+1} \dots a_n]\]

Aplicamos los siguientes pasos algebraicos rigurosos:Por definición de nuestra inducción para $n$ elementos:

\[[a_1 \cdots a_n] = [a_1 \dots a_{n-1}][a_n]\]

Dado que $a_1 \dots a_{n-1}$ contiene $n-1$ elementos (rango menor que $n$), por hipótesis de inducción podemos descomponerlo usando el punto de corte $i$ (ya que $i < n-1$):

\[[a_1 \dots a_{n-1}][a_n] = \Bigl( [a_1 \dots a_i][a_{i+1} \dots a_{n-1}] \Bigr) [a_n]\]

Aplicando el axioma de asociatividad de la ley de composición en $S$ sobre los tres elementos resultantes, reagrupamos los corchetes:

\[\Bigl( [a_1 \dots a_i][a_{i+1} \dots a_{n-1}] \Bigr) [a_n] = [a_1 \dots a_i] \Bigl( [a_{i+1} \dots a_{n-1}][a_n] \Bigr)\]

Por hipótesis de inducción aplicada sobre los últimos $n-i$ elementos (que son estrictamente menos de $n$ elementos), el término de la derecha se fusiona en un solo producto de rango menor:

\[[a_1 \dots a_i] \Bigl( [a_{i+1} \dots a_{n-1}][a_n] \Bigr) = [a_1 \dots a_i][a_{i+1} \dots a_n]\]

Queda demostrado por inducción que la definición es consistente y la propiedad de asociatividad generalizada se cumple para cualquier agrupación10. A partir de este punto, se prescinde de los corchetes escribiendo simplemente $a₁ … a_n$º

—

Elemento identidad (Elemento Neutro)

Un elemento identidad para una ley de composición en $S$ es un elemento $e \in S$ tal que para todo $a \in S$ se cumple que:

\[ea = a \quad \text{y} \quad ae = a\]

Teorema de Unicidad de la identidad

Un conjunto S dotado de una ley de composicion contiene como maximo un elemento identidad.

Demostracion: Supongamos que existen dos elementos identidad distintos, $e y e'$ en $S$.

Debido a que $e$ es un elemento identidad, al componerlo con cualquier elemento (en particular con $e'$) lo deja inalterado por la izquierda:

\[ee' = e'\]
Debido a que $e'$ es un elemento identidad, al componerlo con cualquier elemento (en particular con $e$) lo deja inalterado por la derecha.

\[ee' = e\]

Igualando ambas expresiones a traves del termino comun $ee'$, concluimos que:

\[e = e'\]

Por lo tanto, la identidad es unica. Se denota habitualmente por 1 si la ley se escribe multiplicativamente, o por 0 si se escribe aditivamente.

—

Inversibilidad

Supongamos que la ley de composicion en $S$ es asociativa y posee un elemento identidad 1. Un elemento $a \in S$ se define como invertible si existe un elemento $b \in S$ tal que satisface la doble condicion:

\[ab = 1\] y \[ba = 1\]

En tal caso, $b$ se denomina el inverso de a y se denota para $a^{-1}$ (o por $-a$ en notacion aditiva)

Teorema de Unicidad del Inverso a partir de Inversos Laterales

Si un elemento $a \in S$ posee tanto un inverso izquierdo $\ell \in S$ (tal que $\ell a = 1$) como un inverso derecho $r \in S$ (tal que $ar = 1$), entonces $\ell = r$, el elemento $a$ es invertible, y su inverso es unico.

Demostracion: Utilizando la existencia de la identidad, la propiedad asociativa y las definiciones de los inversos laterales, realizamos la siguiente cadena de igualdades.

\[\ell = \ell \cdot 1 = \ell(ar) = (\ell a)r = 1 \cdot r = r\]

Esto demuestra que el inverso izquierdo y el derecho coinciden necesariamente, obligando a que cualquier inverso sea unico.

Propiedades algebraicas de los inversos:

Inversos del producto: Si $a$ y $b$ son elementos invertibles en $S$, entonces su producto $ab$ tambien es invertible, y su inverso es el producto de los inversos en orden opuesto:

\[(ab)^{-1 }^{}= b^{-1}a^{-1}\]

Demostracion:

\[(ab)(b^{-1}a^{-1}) = a(bb^{-1})a^{-1}_{} = a(1)a^{-1} = aa^{-1} = 1\]

\[(b^{-1}a^{-1})(ab) = b^{-1}(a^{-1}a)b = b^{-1}(1)b = b^{-1}b = 1\]
Inversos laterales sin inversibilidad global: Un elemento puede poseer un inverso izquierdo o un inverso derecho sin ser invertible glabalmente. Un ejemplo clasico de esto es el mapeo de desplazamiento por la derecha (shift map) $s: \mathbb{N} \to \mathbb{N}$ definido por $s(n) = n + 1$, el cual posee infinitos inversos izquierdos pero ningun inverso derecho.

—

Notación de Potencias

Para cualquier ley de composición asociativa, se define la notación de potencias de un elemento $a$ como sigue:

Para un entero $n > 0$: $a^n = \underbrace{a \cdot a \cdots a}_{n \text{ factores}}$.
Si $a$ es invertible, para $n > 0$: $a^{-n} = \underbrace{a^{-1} \cdot a^{-1} \cdots a^{-1}}_{n \text{ factores}}$.
Para el exponente cero: $a^0 = 1$ (el elemento identidad).

Bajo estas definiciones, se cumplen de manera rigurosa las leyes usuales de los exponentes para todo $r, s \in \mathbb{Z}$:

\[a^r a^s = a^{r+s} \quad \text{y} \quad (a^r)^s = a^{rs}\]

Si la ley se escribe utilizando la notación aditiva, la potencia $a^n$ se reemplaza de manera equivalente por la notación de múltiplo:

\[na = \underbrace{a + a + \dots + a}_{n \text{ sumandos}}\]

—

Propiedades Elementales Inmediatas

A partir de los axiomas fundamentales de grupo, se derivan de forma estrictamente lógica los siguientes teoremas

Proposición 2.2.3 (Ley de Cancelación)

Sean $a, b, c$ elementos de un grupo $G$.

Si $ab = ac$, entonces $b = c$.
Si $ba = ca$, entonces $b = c$.
Si $ab = a$ o $ba = a$, entonces $b = 1$.

Demostración

Supongamos que $ab = ac$. Dado que $a \in G$, existe un elemento inverso $a^{-1} \in G$. Multiplicando a la izquierda en ambos miembros de la igualdad por $a^{-1}$: \[a^{-1}(ab) = a^{-1}(ac)\]

\[a^{-1}(ab) = a^{-1}(ac)\]

Aplicando el axioma de asociatividad: \[(a^{-1}a)b = (a^{-1}a)c\]

\[(a^{-1}a)b = (a^{-1}a)c\]

Por definición de inverso, $a^{-1}a = 1$:

\[1b = 1c\]

Por definición del elemento identidad, $1b = b$ y $1c = c$, por lo que concluimos que: \[b = c\]

\[b = c\]

La demostración para la cancelación por la derecha ($ba = ca \implies b = c$) es análoga, multiplicando por $a^{-1}$ por la derecha.

Para la última afirmación, si $ab = a$, podemos escribirlo como $ab = a1$ por propiedad de la identidad. Aplicando la ley de cancelación por la izquierda para el elemento $a$, obtenemos directamente $b = 1$.

—

Grupos Abelianos y Orden de un Grupo

Un grupo $G$ se denomina abeliano (o conmutativo) si su ley de composición satisface el axioma de conmutatividad: $ab = ba$ para todo $a, b \in G$

Orden de un Grupo ($|G|$): Es la cardinalidad del conjunto $G$ (el número de elementos que contiene). Si esta cantidad es finita, $G$ es un grupo finito; en caso contrario, se denomina grupo de orden infinito.

Ejemplos Fundamentales de Grupos de Orden Infinito:

$(\mathbb{Z}, +)$: El grupo aditivo de los enteros (abeliano). Su identidad es $0$ y el inverso de $a$ es $-a$.
$(\mathbb{R}^\times, \cdot)$: El grupo multiplicativo de los números reales no nulos (abeliano). El elemento aditivo $0$ se excluye dado que no posee inverso multiplicativo.
$GL_n(\mathbb{R})$: El Grupo General Lineal, conformado por todas las matrices reales de tamaño $n \times n$ invertibles bajo la multiplicación de matrices. Es un grupo no abeliano para todo $n > 1$.

—

El Grupo Simétrico $S_3$

El grupo simétrico $S_n$ es el grupo de todas las aplicaciones biyectivas (permutaciones) de un conjunto de $n$ elementos en sí mismo. El orden de $S_n$ es exactamente $n!$.

El grupo $S_3$ posee orden $3! = 6$. Es el grupo no abeliano más pequeño que existe

Presentación de $S_3$ por Generadores y Relaciones

Podemos caracterizar completamente a $S_3$ utilizando dos elementos generadores

Un elemento $x$ de orden 3 (la permutación cíclica $(123)$).
Un elemento $y$ de orden 2 (la transposición $(12)$).

Estos generadores satisfacen de forma estricta las siguientes relaciones algebraicas de definición:

\[x^3 = 1, \quad y^2 = 1, \quad yx = x^2y\]

A partir de estas relaciones, se deduce rigurosamente que los seis elementos distintos del grupo son:

\[S_3 = \{1, x, x^2, y, xy, x^2y\}\]

Prueba de que los 6 elementos son mutuamente distintos:

Supongamos por contradicción que dos elementos de la lista son iguales. Si tuviéramos $xy = x^2y$, multiplicando por el inverso $y^{-1}$ (que es $y$, dado que $y^2=1$) por la derecha en ambos lados, obtendríamos $x = x^2$. Multiplicando por $x^{-1}$ se reduce a $1 = x$, lo cual contradice que $x$ sea un elemento de orden 3. Mediante el uso sistemático de la ley de cancelación, se demuestra que ninguna de las seis expresiones listadas puede colapsar en otra, garantizando que el orden del grupo es exactamente 6.

El comportamiento no abeliano de $S_3$:

La relación $yx = x^2y$ muestra explícitamente la no conmutatividad. Dado que $x^2 \neq x$, se concluye de inmediato que: \[yx \neq xy\]

\[yx \neq xy\]

Ejemplo de Cálculo Algebraico en $S_3$:

Cualquier producto de potencias de $x$ e $y$ se puede simplificar para expresarse en la forma estándar $x^i y^j$ (con $0 \le i < 3$ y $0 \le j < 2$) moviendo sistemáticamente las $y$ hacia la derecha utilizando la regla $yx = x^2y$ y reduciendo los exponentes con $x^3 = 1$ e $y² = 1$11. Por ejemplo, simplifiquemos la expresión $x^{-1}y^3x^2y$

Como $x^3 = 1$, su inverso es $x^{-1} = x^2$

Como $y^2 = 1$, entonces $y^3 = y^2 \cdot y = 1 \cdot y = y$.

Sustituyendo en la expresión original, tenemos:

\[x^{-1}y^3x^2y = x^2(y x^2) y\]

Reescribimos $yx^2$ como $(yx)x = (x^2y)x = x^2(yx) = x^2(x^2y) = x^4y = xy$ (ya que $x^4 = x^3 \cdot x = x$).

Sustituyendo esto de vuelta:

\[x^2(yx^2)y = x^2(xy)y = x^3y^2\]

Dado que $x^3 = 1$ e $y^2 = 1$, concluimos que:

\[x^{-1}y^3x^2y = 1\]

Definición de un Subgrupo

Un subconjunto $H$ de un grupo $G$ es un subgrupo (denotado por $H \le G$) si cumple con las propiedades de grupo bajo la ley de composición heredada de $G$ Formalmente, $H$ es un subgrupo de $G$ si y solo si satisface las siguientes tres condiciones de consistencia.

Clausura: Si $a, b \in H$, entonces $ab \in H$.
Identidad: El elemento identidad de $G$ pertenece al subconjunto: $1 \in H$.
Inversos: Si $a \in H$, entonces su inverso en el grupo también pertenece al subconjunto: $a^{-1} \in H$.

No es necesario verificar el axioma de asociatividad para $H$, dado que la operación ya es asociativa sobre todo el conjunto $G$, y por lo tanto esta propiedad se hereda de manera natural para cualquier subconjunto

Ejemplos de Subgrupos:

Subgrupos Triviales: Todo grupo $G$ contiene siempre dos subgrupos triviales: el propio grupo $G$ y el subgrupo que consta únicamente del elemento identidad $\{1\}$.
Grupo Especial Lineal ($SL_n(\mathbb{R})$): El conjunto de matrices reales $n \times n$ con determinante igual a 1 es un subgrupo del Grupo General Lineal $GL_n(\mathbb{R})$.
Prueba rápida de clausura: Si $A, B \in SL_n(\mathbb{R})$, entonces $\det(A) = 1$ y $\det(B) = 1$. Por la propiedad multiplicativa del determinante, $\det(AB) = \det(A)\det(B) = 1 \cdot 1 = 1$, lo que demuestra que $AB \in SL_n(\mathbb{R})$.

Mapeo Bilineal

Para comprender qué es un mapeo bilineal, conviene descomponer el término en sus tres componentes principales:

Mapeo (Función): Una regla matemática que toma elementos de un conjunto de entrada (dominio) y los transforma para generar un elemento en un conjunto de salida (codominio).
Linealidad: Una función es lineal cuando respeta la adición y la multiplicación por escalares. Es decir, si se suman dos entradas, la salida es la suma de las salidas individuales; y si se escala la entrada por un número, la salida se escala en la misma proporción.
Bilineal ("Bi" = Dos): Un mapeo bilineal es una función que procesa dos entradas independientes (procedentes del producto cartesiano de dos espacios vectoriales) para obtener un elemento en un tercer espacio vectorial, caracterizándose por ser lineal respecto a cada una de sus dos entradas por separado.

—

Definición Formal, Dominio y Codominio

Formalmente, sean $X$, $Y$ y $Z$ tres espacios vectoriales.

Un mapeo bilineal se define como la función: \[B: X \times Y \longrightarrow Z\].

\[B: X \times Y \longrightarrow Z\]

La función toma un par ordenado de vectores $(\vec{u}, \vec{v})$ con $\vec{u} \in X$ y $\vec{v} \in Y$, y devuelve un único vector en el espacio $Z$.

—

Los Tres Axiomas Fundamentales de la Bilinealidad

Para que la función $B$ sea calificada formalmente como un mapeo bilineal, debe satisfacer de manera estricta los siguientes tres axiomas algebraicos:

Axioma 1: Aditividad en la Primera Coordenada

Si se fija el segundo argumento $z$, la función actúa como una transformación aditiva sobre el primer argumento:

\[B(x + y, z) = B(x, z) + B(y, z) \quad (\forall x, y \in X, \, z \in Y)\]

Sumar dos vectores antes de evaluar la función en el primer argumento equivale a evaluar cada vector por separado y luego sumar los resultados.

Axioma 2: Aditividad en la Segunda Coordenada

Si se fija el primer argumento $x$, la función es aditiva sobre el segundo argumento:

\[B(x, y + z) = B(x, y) + B(x, z) \quad (\forall x \in X, \, y, z \in Y)\]

La propiedad distributiva se cumple de manera idéntica e independiente en la segunda entrada.

Axioma 3: Preservación del Escalamiento (Homogeneidad)

Para cualquier escalar $c$ y cualesquiera vectores $x \in X$ e $y \in Y$, el escalar se puede extraer fuera de la función o trasladar al otro argumento:

\[B(cx, y) = c \cdot B(x, y) = B(x, cy)\]

Escalar cualquiera de los dos vectores por una constante $c$ produce un resultado global multiplicado por la misma constante $c$

Expresión General Expandida

Al combinar simultáneamente la aditividad y el escalamiento sobre ambas entradas, se obtiene la regla distributiva general de los mapeos bilineales

Dados los escalares $a, b, c, d$ y los vectores $\vec{u}, \vec{v} \in X$ y $\vec{s}, \vec{t} \in Y$:

\[B(a\vec{u} + b\vec{v}, \, c\vec{s} + d\vec{t}) = ac \cdot B(\vec{u}, \vec{s}) + ad \cdot B(\vec{u}, \vec{t}) + bc \cdot B(\vec{v}, \vec{s}) + bd \cdot B(\vec{v}, \vec{t})\]

Esta identidad muestra cómo la bilinealidad permite descomponer combinaciones lineales compuestas de manera análoga a la multiplicación binomial en el álgebra elemental.

Ejemplo ilustrativo de Mapeos Bilineales

Multiplicacion de numeros reales: Si se consideran los numeros reales $\mathbb{R}$ como un espacio vectorial sobre si mismos, la funcion de multiplicacion

$f: \mathbb{R} \times \mathbb{R} \to \mathbb{R}$ dada por $f(x, y) = x \cdot y$ es un mapeo bilineal básico:

Primera coordenada: $B(x+y, z) = (x+y)\cdot z = x\cdot z + y\cdot z = B(x, z) + B(y, z)$
Segunda coordenada: $B(x, y+z) = x\cdot (y+z) = x\cdot y + x\cdot z = B(x, y) + B(x, z)$
Escalamiento: $B(cx, z) = (cx)\cdot z = c\cdot(xz) = x\cdot(cz) = B(x, cz)$.

El producto interno (Producto Punto): El producto escalar o producto interno restringido a valores reales entre vectores es un ejemplo fundamental de mapeo bilineal.

Multiplicacion de Matrices: La multiplicacion de matrices combina elementos de dos espacios vectoriales de matrices para generar un elemento en un tercer espacio, siendo lineal en cada factor.

—

Rol y aplicacion en criptografia

En la informatica y la seguridad de la informacion, los mapeos bilineales constituyen la piedra angular de la criptografia basada en emparejamiento.

Resolución de problemas criptográficos: Se emplean específicamente para resolver el Problema del Logaritmo Discreto (DLP) y mitigar ataques como el ataque MOV en la criptografía de curvas elípticas (ECC).
Cifrado Basado en Identidad (IBE): Permite esquemas donde la clave pública puede ser directamente la identidad o correo del usuario, incluyendo IBE jerárquico, firmas en anillo basadas en ID, firmas ciegas basadas en ID y hashes basados en ID.
Esquemas de Firma Avanzados: Habilita la creación de firmas cortas (que reducen el tamaño de la firma a la mitad en comparación con las originales), multifirmas, firmas agregadas, firmas ciegas y firmas basadas en árboles de autenticación.

—

Funcionalidades

El Cifrado Funcional (FE) es un paradigma moderno en criptografía de clave pública. A diferencia del cifrado tradicional (donde se descifra todo el texto plano o nada), en FE una clave secreta permite calcular el valor de una función específica sobre los datos cifrados sin revelar el contenido original completo.

Cifrado Basado en Predicados (Predicate Encryption):
Las claves secretas $SK_f$ corresponden a predicados booleanos $f$, mientras que los textos cifrados se asocian a vectores de atributos $I$.
Un usuario posee la clave secreta $SK_f$ y puede evaluar exitosamente el texto cifrado asociado a $I$ si y solo si $f(I) = 1$
Prueba de Igualdad (Equality Test - FE-ET):
Es una subcategoría de FE definida sobre un espacio de claves de función $K$ y un espacio de mensajes $X$ mediante la funcionalidad.

\[f(k \in K; x \in X) = \begin{cases} 1 & \text{si } k = x \\ 0 & \text{en otro caso} \end{cases}\]

Fundamental para la búsqueda de información en bases de datos cifradas (Searchable Encryption) en la nube, permitiendo saber si un texto cifrado coincide con una consulta sin revelar el mensaje subyacente.

Prueba de Desigualdad (Inequality Test):

Permite determinar si dos elementos pertenecientes a un conjunto totalmente ordenado $(S, \le)$ satisfacen relaciones como $a > b$, $a \ge b$ o $a \neq b$.

Utilizada para consultas de rango y comparaciones ordenadas en la nube.

—

Teorema de Wiener (Paley–Wiener)

Relaciona las propiedades de decaimiento en el infinito de una función o distribución con la analiticidad de su transformación de Fourier (utilizando la transformada de Fourier holomorfa sobre clases de funciones de cuadrado integrable en la recta real)

Pruebas de Primalidad (Primality Tests)

Para generar parámetros en RSA, Diffie-Hellman o DSA, es indispensable verificar eficientemente si un entero positivo es primo.

Método Escolar (School Method)

Algoritmo determinista trivial que verifica la divisibilidad de $n$ por todos los números entre $2$ y $n-1$ (o $\sqrt{n}$). Es de complejidad exponencial respecto al número de bits.

Prueba de Primalidad de Solovay–Strassen:

Naturaleza: Algoritmo probabilístico basado en los pseudoprimos de Euler-Jacobi
Criterio de Euler: Para todo número primo $p$ y entero $a$.

\[a^{(p-1)/2} \equiv \left( \frac{a}{p} \right) \pmod p\]

donde $\left( \frac{a}{p} \right)$ es el símbolo de Jacobi/Legendre.

El Problema del Logaritmo Discreto (DLP) en Subgrupos de $\mathbb{Z}_p^*$

Dado un grupo cíclico multiplicativo $G = \mathbb{Z}_p^*$ generado por $g$, y un elemento $e \in G$, el DLP consiste en encontrar el entero $x$ tal que

\[g^x \equiv e \pmod p\]

Si el orden del grupo ($p-1$) se factoriza únicamente en números primos pequeños (número smooth o suave), el Algoritmo de Pohlig–Hellman resuelve el DLP eficientemente reduciendo el problema a subgrupos pequeños.
Para evitar este ataque, $p$ debe elegirse como un primo seguro (safe prime), definido como $p = 2q + 1$, donde $q$ es también un primo grande. e requieren tamaños de $p$ de entre 1024 y 3072 bits

Algoritmo Baby-Step Giant-Step (BSGS)

Es un algoritmo genérico de intercambio espacio-tiempo (space-time tradeoff) diseñado por Daniel Shanks para calcular logaritmos discretos en un grupo abeliano finito $G$ de orden $n$.

Descomposición del Exponente: Sea $m = \lceil \sqrt{n} \rceil$. Expresamos $x$ como $x = im + j$, con $0 \le i < m$ y $0 \le j < m$.
Ecuación Fundamental:

\[\alpha^x = \beta \iff \alpha^{im+j} = \beta \iff \alpha^j = \beta \cdot (\alpha^{-m})^i\]

Fases del Algoritmo:
- Baby Steps: Precalcula y almacena en una tabla Hash los valores $(j, \alpha^j)$ para $0 \le j < m$
- Giant Steps: Evalúa $\beta \cdot (\alpha^{-m})^i$ para $i = 0, 1, \dots, m-1$ hasta encontrar una coincidencia con la tabla.
Complejidad: Requiere $O(\sqrt{n})$ tiempo de cómputo y $O(\sqrt{n})$ espacio de memoria.

Criba de Campos de Funciones (Function Field Sieve - FFS)

Presentado en 1994 como un método subexponencial para resolver el DLP en campos finitos de característica pequeña ($\mathbb{F}_{p^n}$ con $p$ pequeño). Adapta la criba de enteros utilizando polinomios y secuencias de código Gray.

Factorización por Curvas Elípticas (ECM / Método de Lenstra)

Algoritmo subexponencial de factorización de enteros inventado por H. W. Lenstra Jr. Es el método más eficiente para encontrar factores primos pequeños $p$ (de 10 a 40 dígitos decimales).

Ventaja sobre el Algoritmo $p-1$ de Pollard:

El algoritmo $p-1$ de Pollard falla si $p-1$ contiene factores primos grandes.

ECM reemplaza el grupo multiplicativo fijo $\mathbb{Z}_p^*$ (de orden $p-1$) por el grupo de puntos de una curva elíptica aleatoria $E(\mathbb{F}_p)$.

Por el Teorema de Hasse, el orden $\#E(\mathbb{F}_p) = p + 1 - a$ varía dentro del intervalo $[p + 1 - 2\sqrt{p}, p + 1 + 2\sqrt{p}]$. Si para alguna curva seleccionada el orden $\#E(\mathbb{F}_p)$ resulta ser suave (smooth), la multiplicación escalar $[k]P$ módulo $n$ encontrará un elemento no invertible, revelando el factor mediante $\gcd(\text{denominador}, n)$.